﻿namespace Leetcode.N0044;
public class Solution
{
    public bool IsMatch(string s, string p)
    {

        var tokenList = this.GetToken(p);
        int sIndex = 0;
        for (int i = 0; i < tokenList.Count; i++)
        {
            var token = tokenList[i];
            if (token == "*")
            {
                continue;
            }

            int j;

            if (i == 0)
            {
                j = this.StartWith(s, sIndex, token);
                if (j == -1 || (tokenList.Count == 1 && s.Length != p.Length))
                {
                    return false;
                }
            }
            else if (i == tokenList.Count - 1)
            {
                j = this.EndWith(s, sIndex, token);
            }
            else
            {
                j = this.First(s, sIndex, token);
            }

            if (j == -1)
            {
                return false;
            }
            sIndex = j + token.Length;
        }

        return tokenList.Count > 0 || s.Length == 0;
    }

    private IList<string> GetToken(string p)
    {
        var token = new List<string>();

        for (var i = 0; i < p.Length; i++)
        {
            if (p[i] == '*')
            {
                token.Add("*");
                continue;
            }
            int j;
            for (j = i; j < p.Length - 1; j++)
            {
                if (p[j + 1] == '*')
                {
                    break;
                }
            }
            token.Add(p.Substring(i, j - i + 1));
            i = j;
        }
        return token;
    }

    private int StartWith(string s, int fromIndex, string searchString)
    {
        if (s.Length - fromIndex < searchString.Length)
        {
            return -1;
        }

        int i = fromIndex;
        for (var j = 0; j < searchString.Length; j++)
        {
            if (searchString[j] != '?' && searchString[j] != s[i])
            {
                return -1;
            }
            i++;
        }
        return fromIndex;
    }

    private int EndWith(string s, int fromIndex, string searchString)
    {
        if (s.Length - fromIndex < searchString.Length)
        {
            return -1;
        }

        int i = s.Length - 1;
        for (var j = searchString.Length - 1; j >= 0; j--)
        {
            if (searchString[j] != '?' && searchString[j] != s[i])
            {
                return -1;
            }
            i--;
        }
        return i + 1;
    }

    private int First(string s, int fromIndex, string searchString)
    {
        for (var i = fromIndex; i <= (s.Length - searchString.Length); i++)
        {
            int j;
            for (j = 0; j < searchString.Length; j++)
            {
                if (searchString[j] != '?' && searchString[j] != s[i + j])
                {
                    break;
                }
            }
            if (j == searchString.Length)
            {
                return i;
            }
        }
        return -1;
    }

}
